/*
 * @Author: kaikaima
 * @Date: 2020-12-01 18:17:51
 * @LastEditTime: 2021-01-04 19:50:18
 * @LastEditors: Please set LastEditors
 * @Description: test
 * @FilePath: /undefined/home/messi/Data_Structure_and_Algorithm_GIT/Tree/RBT.h
 */
#include "BST.h"

#ifndef __hhxxttxs_RBT__
#define __hhxxttxs_RBT__

template <class T>
class RedBlackTree : public BinaryTree<T>
{
private:
    typedef typename BinaryTree<T>::Node Node;
    void right_rotation (Node* _x);
    void left_rotation (Node* _x);
    void recolor (Node* _x);
    void del (Node* _x);
public:
    RedBlackTree() : BinaryTree<T>() {};
    RedBlackTree(T _data) : BinaryTree<T>(_data) {};
    void insert (T _data);
    void del_data (T _data);
    //void draw () const;
};

template <class T>
void RedBlackTree<T>::right_rotation(RedBlackTree<T>::Node* _x)
{
    Node* _y = _x->lc;
    /**
     * @description: function "change" will only change _x's parent's child
     */
    this->change(_x, _y);
    _x->parent=_y;
    _y->rc->parent=_x;
    _x->lc=_y->rc;
    _y->rc=_x;
};

template <class T>
void RedBlackTree<T>::left_rotation(RedBlackTree<T>::Node* _x)
{
    Node* _y = _x->rc;
    this->change(_x, _y);
    _x->parent=_y;
    _y->lc->parent=_x;
    _x->rc=_y->lc;
    _y->lc=_x;
};

template <class T>
void RedBlackTree<T>::recolor(RedBlackTree<T>::Node* _x)
{
    if(_x->rc->color==RED && _x->lc->color==RED)
    {
        _x->color=RED;
        _x->rc->color=_x->lc->color=BLACK;
    }  
};

template <class T>
void RedBlackTree<T>::del(Node* _x)
{
    if(_x==NULL || _x==this->nil)
        return;
    if(_x->lc==_x->rc/*==this->nil*/){
        if(_x->color==RED)//_x will not be the root
        {
            this->change(_x,this->nil);
            delete _x;
        }
        else{
            Node* x=_x->rc;
            _x->rc->parent=_x->parent;
            this->change(_x,_x->rc);
            delete _x;
            while(x!=this->root && x->color==BLACK){
                bool key = (x==x->parent->lc);
                Node* brother=(x==x->parent->lc)?(x->parent->rc):(x->parent->lc);
                if(brother->color==RED){
                    brother->color=BLACK;
                    x->parent->color=RED;
                    if(key){
                    left_rotation(x->parent);
                    brother=x->parent->rc;}
                    else{
                    right_rotation(x->parent);
                    brother=x->parent->lc;}
                }
                if(brother->lc->color==BLACK && brother->rc->color==BLACK){
                    brother->color=RED;
                    x=x->parent;}
                else if(key){
                    if(brother->rc->color==BLACK){
                        brother->lc->color=BLACK;
                        brother->color=RED;
                        right_rotation(brother);
                        brother=x->parent->rc;
                    }
                    brother->color=x->parent->color;
                    x->parent->color=BLACK;
                    brother->rc->color=BLACK;
                    left_rotation(x->parent);
                    x=this->root;
                }
                else{
                    if(brother->lc->color==BLACK){
                        brother->rc->color=BLACK;
                        brother->color=RED;
                        left_rotation(brother);
                        brother=x->parent->rc;
                        }
                    brother->color=x->parent->color;
                    x->parent->color=BLACK;
                    brother->lc->color=BLACK;
                    right_rotation(x->parent);
                    x=this->root;
                }
            }
        }
        return;
    }
    if(_x->lc==this->nil || _x->rc==this->nil)
    {
        Node* child = (_x->lc==this->nil)?(_x->rc):(_x->lc);
        _x->data=child->data;
        _x->lc=_x->rc=this->nil;
        delete child;
    }
    else{
        Node* p = this->min(_x->rc);
        _x->data=p->data;
        del(p);//p will not have left child
    }
};
/*  from <Introduction to Algorithms>
{
    Node* y=_x;
    bool original = y->color;
    Node* x=_x->lc;
    if(_x->lc==this->nil){
        x=_x->rc;
        _x->rc->parent=_x->parent;
        this->change(_x,_x->rc);
    }
    else if(_x->rc==this->nil)
    this->change(_x,_x->lc);
    else
    {
        y=this->min(_x->rc);
        original=y->color;
        x=y->rc;
        /*if(y->parent==_x)
        x->parent=y;
        else*//*
        y->rc->parent=y->parent;
        this->change(y,y->rc);
        y->rc=_x->rc;
        y->rc->parent=y;
        this->change(_x,y);
        y->lc=_x->lc;
        y->lc->parent=y;
        y->color=_x->color;
    }
    delete _x;
    if(original==BLACK)
    {
        while(x!=this->root && x->color==BLACK){
            bool key = (x==x->parent->lc);
            Node* brother=(x==x->parent->lc)?(x->parent->rc):(x->parent->lc);
            if(brother->color==RED){
                brother->color=BLACK;
                x->parent->color=RED;
                if(key){
                    left_rotation(x->parent);
                    brother=x->parent->rc;}
                else{
                    right_rotation(x->parent);
                    brother=x->parent->lc;}
                }
            if(brother->lc->color==BLACK && brother->rc->color==BLACK){
                brother->color=RED;
                x=x->parent;}
            else if(key){
                if(brother->rc->color==BLACK){
                    brother->lc->color=BLACK;
                    brother->color=RED;
                    right_rotation(brother);
                    brother=x->parent->rc;
                    }
                brother->color=x->parent->color;
                x->parent->color=BLACK;
                brother->rc->color=BLACK;
                left_rotation(x->parent);
                x=this->root;
                }
            else{
                if(brother->lc->color==BLACK){
                    brother->rc->color=BLACK;
                    brother->color=RED;
                    left_rotation(brother);
                    brother=x->parent->rc;
                    }
                brother->color=x->parent->color;
                x->parent->color=BLACK;
                brother->lc->color=BLACK;
                right_rotation(x->parent);
                x=this->root;
                }
        }
        x->color=BLACK;
    }
}*/

/*
 * 
 *    ┏┓　　　┏┓
 *  ┏┛┻━━━┛┻┓
 *  ┃　　　　　　　┃
 *  ┃　　　━　　　┃
 *  ┃　＞　　　＜　┃
 *  ┃　　　　　　　┃
 *  ┃...　⌒　...　┃
 *  ┃　　　　　　　┃
 *  ┗━┓　　　┏━┛
 *      ┃　　　┃　
 *      ┃　　　┃
 *      ┃　　　┃  分割符——private vs public
 *      ┃　　　┃  神兽保佑
 *      ┃　　　┃  代码无bug　　
 *      ┃　　　┃
 *      ┃　　　┗━━━┓
 *      ┃　　　　　　　┣┓
 *      ┃　　　　　　　┏┛
 *      ┗┓┓┏━┳┓┏┛
 *        ┃┫┫　┃┫┫
 *        ┗┻┛　┗┻┛
 */


template <class T>
void RedBlackTree<T>::insert(T _data)
{
    if(this->root==this->nil){
        Node* p = new Node(_data);
        p->lc=p->rc=this->nil;
        this->root=p;
        return;
    }
    Node* z = this->data_insert(_data);
    while(z->parent!=NULL && z->parent->color==RED)//z has its grandpa because root's color is black
    {
    if(z->parent==z->parent->parent->lc){
        Node* uncle=z->parent->parent->rc;
        if(uncle->color==RED){
            recolor(z->parent->parent);
        /**
         * @description: then rejudge uncle's parent.
         * @param {*}
         * @return {*}
         */
            z=z->parent->parent;
        }
        else{
        if(z==z->parent->rc){
            /**
             * @description: z always points the third-generation.
             * @param {*}
             * @return {*}
             */
            z=z->parent;
            left_rotation(z);
        }
        z->parent->color=BLACK;
        z->parent->parent->color=RED;
        right_rotation(z->parent->parent);
        break;
        }}
    else
    /**
     * @description: do the same thing expect changing left and right
     * @param {*}
     * @return {*}
     */
    {
        Node* uncle=z->parent->parent->lc;
        if(uncle->color==RED){
            recolor(z->parent->parent);
            z=z->parent->parent;
        }
        else{
        if(z==z->parent->lc){
            z=z->parent;
            right_rotation(z);
        }
        z->parent->color=BLACK;
        z->parent->parent->color=RED;
        left_rotation(z->parent->parent);
        break;
        }}
    }
    this->root->color=BLACK;
};

template <class T>
void RedBlackTree<T>::del_data(T _data)
{
    del(this->tree_search(_data));
};

#else
//do nothing
#endif